#define PROFESSOR_Vs_CODE

void depthFirst(GraphNode * root, TemplateVector<GraphNode*> & list_out)
{
#ifdef PROFESSOR_Vs_CODE
	GraphNode * cursor = root, * n, * unvisitedNeighbor;
	int index = 0;
	bool beenHere = false;
	// while we have a node we can traverse
	while(cursor)
	{
		// if this node has not beed visited before
		if(!beenHere)
		{
			// visit this node
			list_out.add(cursor);
		}
		// find a neighbor node that has not been visited yet
		unvisitedNeighbor = 0;
		// look through all neighbors until an unvisited neighbor is found
		for(int i = 0; unvisitedNeighbor == 0 && i < cursor->edges.size(); ++i)
		{
			n = cursor->edges.get(i).to;
			// if this neighbor node is not recognized (not in our list)
			if(list_out.indexOf(n) < 0)
			{
				// mark it as an unvisited neighbor
				unvisitedNeighbor = n;
			}
		}
		// if an unvisited neighbor was found
		if(unvisitedNeighbor)
		{
			// that is the next place to visit
			cursor = unvisitedNeighbor;
			// we have not traveled to this node before
			beenHere = false;
		}
		// if this node has no unvisited neighbors
		else
		{
			// back-track in the list... discover where we are in the list
			int currentIndex = list_out.indexOf(cursor);
			// if back-tracking is possible
			if(currentIndex > 0)
			{
				// back-track
				cursor = list_out.get(currentIndex -1);
				// noting that we've been here before
				beenHere = true;
			}
			else
			{
				// otherwise, give up.
				cursor = 0;
			}
		}
	}
#else
	// algorithm from Ohio state (http://www.cse.ohio-state.edu/~gurari/course/cis680/cis680Ch14.html)
	//algorithm  dft(x) 
	//   visit(x) 
	GraphNode * y;
	list_out.add(root);
	//   FOR each y such that (x,y) is an edge DO 
	for(int i = 0; i < root->edges.size(); ++i)
	{
		y = root->edges.get(i).to;
		//     IF y was not visited yet THEN 
		if(list_out.indexOf(y) < 0)
		{
			//        dft(y) 
			depthFirst(y, list_out);
		}
	}
#endif
}

void breadthFirst(GraphNode * root, 
	TemplateVector<GraphNode*> & list_out)
{
#ifdef PROFESSOR_Vs_CODE
	GraphNode * cursor = root, * n;
	int index = 0;
	list_out.add(root);
	// while we have a node we can visit
	while(cursor)
	{
		// look through all this node's neighbors
		for(int i = 0; i < cursor->edges.size(); ++i)
		{
			n = cursor->edges.get(i).to;
			// if an unvisited neighbor node is found
			if(list_out.indexOf(n) < 0)
			{
				// add it to the list of unvisited nodes
				list_out.add(n);
			}
		}
		// if there is a node in the list that hasn't been visited
		if(++index < list_out.size())
		{
			// go to the next un-visited node
			cursor = list_out.get(index);
		}
		else
		{
			// otherwise, there are no more nodes to visit
			cursor = 0;
		}
	}
#else
	// algorithm from wikipedia (http://en.wikipedia.org/wiki/Breadth-first_search)
	//1  procedure BFS(Graph,source):
	GraphNode * v;
	GraphEdge * e;
	GraphNode * w;
	//2      create a queue Q
	TemplateVector<GraphNode*> Q;
	//3      enqueue source onto Q
	Q.add(root);
	list_out.add(root);
	//4      mark source
	root->mark = 1;
	//5      while Q is not empty:
	while(Q.size() > 0)
	{
		//6          dequeue an item from Q into v
		v = Q.pull();
		//7          for each edge e incident on v in Graph:
		for(int i = 0; i < v->edges.size(); ++i)
		{
			e = &(v->edges.get(i));
			//8              let w be the other end of e
			w = e->to;
			//9              if w is not marked:
			if(w->mark != 1)
			{
				//10                 mark w
				w->mark = 1;
				//11                 enqueue w onto Q
				Q.add(w);
				list_out.add(w);
			}
		}
	}
	//12  clear all marks
	for(int i = 0; i < list_out.size(); ++i)
	{
		list_out.get(i)->mark = 0;
	}
#endif
}